package com.xw.class08;

/**
 * @author: xw
 * @create: 2023/2/14 15:11
 * @description: 前缀树
 */
public class Code01_Trie {
    // 测试链接 :

    class Trie{
        class Node {
            public int pass;
            public int end;
            public Node[] nexts;

            public Node() {
                pass = 0;
                end = 0;
                nexts = new Node[26];
            }
        }

        private Node root;

        public Trie() {
            root = new Node();
        }

        /**
         * 插入数据
         * @param word
         */
        public void insert(String word){
            if(null == word){
                return ;
            }
            char[] str = word.toCharArray();
            Node node = root;
            node.pass++;
            int path = 0;
            for (int i = 0; i < str.length; i++) {
                path = str[i] - 'a';
                if(node.nexts[path] == null){
                    node.nexts[path] = new Node();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;
        }

        /**
         * 消除数据
         * @param words
         */
        public void erase(String words){
            if(countWordsEqualsTo(words) != 0){
                char[] chars = words.toCharArray();
                Node node = root;
                root.pass--;
                int path = 0;
                for (int i = 0; i < chars.length; i++) {
                    path = chars[i] - 'a';
                    if(-- node.nexts[path].pass == 0){
                        node.nexts[path] = null;
                        return;
                    }
                    node = node.nexts[path];
                }
                node.end--;
            }
        }

        /**
         * 计算word有几个
         * @param words
         * @return
         */
        public int countWordsEqualsTo(String words){
            if (words == null){
                return 0;
            }
            char[] chars = words.toCharArray();
            Node node =  root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null){
                    return 0;
                }
                node = node = node.nexts[index];
            }
            return node.end;
        }

        /**
         * 计算以pre开头的有几个
         * @param pre
         * @return
         */
        public int countWordsStartingWith(String pre) {
            if (pre == null){
                return 0;
            }
            char[] chars = pre.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }

}
